Given the problem of semantic test simplification is NP-hard,
it is hard to find the optimal solution. Therefore, we
propose \SimpleTest, an efficient algorithm for approximate
optimization, that transforms a failed
test into an easier-to-understand simplified test.
 \SimpleTest cannot
guarantee optimal simplification; however, we empirically show
that this algorithm often generates an optimally simplified test in Section~\ref{sec:evaluation}.

Given a failed test $t$ = $\overline{s}$ $\cup$ $\phi$, where $\overline{s}$
= $s_1$, ..., $s_n$, \SimpleTest
has three basic actions on $t$:

\begin{itemize}

\item \textit{remove($t$, $i$)}: returns a new test
 by removing statement $s_i$ from $t$. For example, if $t$
= $s_1$$s_2$...$s_{i-1}$$s_i$$s_{i+1}$...$s_n$ $\cup$ $\phi$, then
\textit{remove($t$, $i$)} =
$s_1$$s_2$...$s_{i-1}$$s_{i+1}$...$s_n$ $\cup$ $\phi$.

\item \textit{reconstruct($t$, $s_i$, $j$, $s_k$)}: returns a new
test by replacing the $j$-th input variable of statement $s_i$ with the
output variable of statement $s_k$. When applying this operation, $s_i$
must be a method invocation statement which has at least $j$ input variables,
and the output variable of the $k$-th statement must not be $\perp$.
%$\spadesuit$ The the $j$-th variable should be type-compatible.

\item \textit{checkProperty($t$, $\phi$)}: returns \CodeIn{true}
if $t$ $\rightarrow$ $\phi$, and \CodeIn{false} if $t$ $\nrightarrow$ $\phi$.
In our implementation, $\phi$ is a user-provided predicate, which can either be an
assertion statement or an exception thrown at a designated statement.

\end{itemize}

\newcommand{\RmoveRedundant}{RemoveRedundantStmts}

\begin{figure}[t]
\textbf{SimpleTest}\\
\textbf{Input}: a unit test $t$ = $\overline{s}$ $\cup$ $\phi$\\
\textbf{Output}: a simplified test $t'$ = $\overline{s'}$ $\cup$ $\phi$\\
\textbf{Auxiliary Methods:}\\
\hspace{2mm} \textit{getReconstructionIndex($t$, $s_i$, $j$)}: returns the
the index of the first statement in test $t$ whose output variable is
type-compatible with the $j$-th input of statement $s_i$. \\
 \textit{reverseStmtOrder($t$)}: returns the reversed order
 of all statements in a test $t$.\\
\textbf{Invariants:}\\
\hspace{2mm} \textit{checkProperty($t$, $\phi$)} $=$ true\\
\hspace{2mm} \textit{checkProperty($t'$, $\phi$)} $=$ true\\
\vspace{-5mm}
\begin{algorithmic}[1]
\STATE $t'$ $\leftarrow$ \textit{\RmoveRedundant}($t$, $\phi$)
\FOR{each statement $s_i$ in $\|reverseStmtOrder|$($t'$)}
\FOR{each input $j$ in statement $s_i$}
\STATE $replace\_index$ $\leftarrow$ \textit{getReconstructionIndex($t'$, $s_i$, $j$)}
\STATE $t_s$ $\leftarrow$ \textit{reconstruct}($t'$, $s_i$, $j$, $replace\_index$)
\IF{\textit{checkProperty}($t_s$, $\phi$)}
\STATE $t'$ $\leftarrow$ \textit{\RmoveRedundant}($t_s$, $\phi$)
\ENDIF
\ENDFOR
\ENDFOR
\STATE return $t'$
\vspace{-2mm}
\end{algorithmic}
\caption{The \SimpleTest algorithm for semantically simplifying a test. The \textit{\RmoveRedundant} procedure 
is defined in Figure~\ref{fig:algorithm1}.
} \label{fig:algorithm2}
\end{figure}

\begin{figure}[t]
\textbf{\RmoveRedundant}\\
\textbf{Input}: a unit test $t$ = $\overline{s}$ $\cup$ $\phi$\\
\textbf{Output}: a simplified test $t'$ = $\overline{s'}$ $\cup$ $\phi$\\
\textbf{Auxiliary Methods:}\\
\hspace{2mm} \textit{getUnusedStmts($t$)}: returns a set of statements whose
output variables are not used in other statements in a test $t$.\\
\textbf{Invariants:}\\
\hspace{2mm} \textit{checkProperty($t$, $\phi$)} $=$ true\\
\hspace{2mm} \textit{checkProperty($t'$, $\phi$)} $=$ true\\
\vspace{-5mm}
\begin{algorithmic}[1]
\STATE $t'$ $\leftarrow$ $t$
\STATE unremovable\_stmts $\leftarrow$ \{\}
%\STATE redundant\_stmts $\leftarrow$ $\overline{s}$ / \textit{getUnusedStmts}($t'$)
\STATE candidate\_stmts $\leftarrow$ \textit{getUnusedStmts}($t'$)
\WHILE{candidate\_stmts $\neq$ $\emptyset$}
\IF{candidate\_stmts $\subseteq$ unremovable\_stmts}
\STATE break;
\ENDIF
\FORALL{statement $s$ in candidate\_stmts}
\STATE $t_s$ $\leftarrow$ \textit{remove}($t'$, $s$)
\IF{\textit{checkProperty}($t_{s}$, $\phi$)}
\STATE $t'$ $\leftarrow$ $t_{s}$
\ELSE
\STATE unremovable\_stmts $\leftarrow$ unremovable\_stmts $\cup$ $s$
\ENDIF
\ENDFOR
\ENDWHILE
\STATE return $t'$
\vspace{-2mm}
\end{algorithmic}
\caption{Algorithm for removing (some) redundant statements in a test.
} \label{fig:algorithm1}
\end{figure}







The core algorithm, \SimpleTest, is described in Figure~\ref{fig:algorithm2}.
It uses an auxiliary procedure called \textit{\RmoveRedundant} described
in Figure~\ref{fig:algorithm1}.

The \SimpleTest algorithm first syntactically simplifies a given
test by calling the \textit{\RmoveRedundant} auxiliary procedure (line 1).
Then, it  \textit{greedily} reconstructs each statement by replacing its input variables with
 possible alternatives created in the same test (line 4). After each
 reconstruction, the algorithm first checks whether $\phi$ is still satisfied (line 6).
 If the reconstructed test still exhibits $\phi$, \SimpleTest
 calls \textit{\RmoveRedundant} to conduct further synax minimization (line 7). Otherwise,
 it rolls back to the test before reconstruction and continues to replace the next input variable (line 3).


The auxiliary method \textit{\RmoveRedundant} conducts
syntax test minimization by removing all redundant
statements which will not affect the test execution result. The
algorithm first computes a set of statements whose output variables
are not referred in the remaining statements (line 3), then tries to remove each statement of the computed
set from test $t$ (line 9). When a statement is removed, the algorithm immediately executes
the test to validate whether the resulting
test can still exhibit $\phi$ (line 10). The output of \textit{\RmoveRedundant}
is a \textit{syntactically-minimized} test. This \textit{\RmoveRedundant} algorithm differs
from existing syntax-based test simplification algorithms~\cite{Lei:2005, Leitner:2007} in two aspects. First, it does
not use program slicing as~\cite{Leitner:2007} does. Computing a program slice
would be too conservative to identify all removable statements~\cite{Lei:2005}. For example,
in the following code snippet: \CodeIn{Y y = new Y();} \CodeIn{y.callPureNativeCode();}
\CodeIn{assert y.satisfyProperty(); }
both static and dynamic slicing might not determine the second statement \CodeIn{y.callPureNativeCode()}
is removable. Second, unlike~\cite{Lei:2005} that applies delta debugging
to all statements in a test $t$, our algorithm only tries to remove statements that can
be safely removed without resulting in a syntactically-invalid test.
Furthermore,  delta debugging requires the to-be-simplified input 
has the \textit{monotonicity} property, i.e., a superset of any
failure-inducing input should also fail. However, this property 
does not always hold for a failing test. For example, a test consisting of lines 1, 7, 8, and 9 of
Figure~\ref{fig:simplified} fails, but its superset - say, a test consisting
of lines 1, 6, 7, 8, 9 is un-compilable and its execution result is unknown.
Lacking the \textit{monotonicity} property, as we validate through
experiment in section~\ref{sec:evaluation},  makes delta debugging
ineffective in the domain of test simplification. In contrast, the \textit{\RmoveRedundant}
algorithm is highly customized to simplify tests. It is fast, efficient,
and easy to implement, and yields better results.

% than~\cite{Lei:2005} and~\cite{Leitner:2007}.

%The simplifier only removes an operation from the
%sequence if the sequence after the removal is syntactically valid:
%a sequence is syntactically valid if every use of a variable in
%the sequence is preceded by an operation that produces the
%variable.




\vspace{1mm}

\vspace{2mm}{\textsc{\textbf{Theorem 2}}}. {\it The worst-case time complexity of
\SimpleTest is $\mathcal{O}$($n^3$), where $n$ is the number of statements
in a test.}\vspace{1mm}

\vspace{1mm}\noindent{\bf Proof. } (Sketch) Each of the for loop in Figure~\ref{fig:algorithm2}
has an upper bound of $n$ iterations. The for loop in Figure~\ref{fig:algorithm1} has also
an upper bound of $n$ iterations. Therefore, the cost of the entire
\SimpleTest algorithm is $\mathcal{O}$($n^3$). $\Box$

\subsection{Example}



We use the simple example in Figure~\ref{fig:failedtest} to illustrate how \SimpleTest
works. Since the test in Figure~\ref{fig:failedtest} is already syntactically-minimized,
\SimpleTest starts from the reconstruction step at line 2 of Figure~\ref{fig:algorithm2}.
Iterating in a reversed order of all statements, \SimpleTest starts to seek
a replaceable variable for \CodeIn{var7} at line 9. After concluding that no existing alternatives 
can replace \CodeIn{var7}, \SimpleTest continues to replace the input variables \CodeIn{var7}
and \CodeIn{var6} at line 8. As a result, \SimpleTest can not find replacement candidates
 for \CodeIn{var7}, but it finds all variables (\CodeIn{var1}--\CodeIn{var7}) can be used to
replace \CodeIn{var6} (the \CodeIn{add} method requires
an \CodeIn{Object}-type argument). Using a heuristic,
the \textit{getReconstructionIndex} method returns the first
available variable \CodeIn{var1} to replace \CodeIn{var6}.
After this replacement, \SimpleTest re-executes the reconstructed test and finds
the assertion at line 10 still fails. \SimpleTest invokes procedure \textit{\RmoveRedundant} to
perform syntax test simplification, yielding the final output as shown
in Figure~\ref{fig:simplified}.


\subsection{Optimization}
\label{sec:opt}

\SimpleTest adapts one straightforward optimization to use delta debugging~\cite{Zeller:2002} to
remove irrelevant array elements. For example, after applying delta debugging,
\SimpleTest simplifies the following syntactically-minimized test code:

\vspace{1mm}


\CodeIn{    int var1 = 0;}

\CodeIn{    int var2 = -1;}

\CodeIn{    int var3 = 2;}

\CodeIn{    int[] vars = new int\{var1, var2, var3\}}

\CodeIn{    boolean r = checkNonNegative(vars);}

\CodeIn{    assertTrue (r); } // \textbf{$\phi$: this assertion fails}

\hspace{23mm} $\Downarrow$


\CodeIn{    int var2 = -1;}

\CodeIn{    int[] vars = new int\{var2\}}

\CodeIn{    boolean r = checkNonNegative(vars);}

\CodeIn{    assertTrue (r); } // \textbf{$\phi$: this assertion fails}

\vspace{3mm}


We find this optimization useful in simplifying
tests for array-related applications in Section~\ref{sec:result}.

\subsection{Avoid Trivial Tests}

\SimpleTest uses variable replacement to simplify a test. However,
if a variable can be replaced without any constraints,
\SimpleTest may create a trivial test like:

\CodeIn{Object a = null;}

\CodeIn{assertTrue (a != null); }

The above test, though perfectly satisfies the failure-revealing property,
is meaningless to programmers. To avoid creating such trivial tests,
we add three constraints to \SimpleTest:

\begin{itemize}

\item Any input variables referred by
the predicate $\phi$ should never be replaced. Variables used
in a testing oracle
 are inherently interesting to programmers. Replacing
 them with new ones is likely to change the original test intentions.

% it is improbable
%to replace that with a new one.

\item The declared value in
a value declaration statement (e.g., the \CodeIn{new Object()} at line 1 of
Figure~\ref{fig:simplified}) should not be replaced. This is because
a declared value is often closely related to the intended testing logic.
Altering a declared value may substantially change the original
 testing intentions, and results in trivial test as the above case.

\item The test code structure should not be changed.
 Specially,  \SimpleTest should not
attempt to create a new statement, re-order existing statements, or change a method
invocation statement to a value declaration statement and vice versa.
This constraint prevents \SimpleTest arbitrarily altering the test code.

\end{itemize}

As shown by our experimental results in Section~\ref{sec:result}, these three constraints
are sufficient to prevent \SimpleTest from outputting trivial tests. None of
the simplified tests of our subject programs produced by \SimpleTest can be regarded as trivial.



\subsection{Discussions}

%$\spadesuit$ \textbf{need to discuss whether the simplified test is revealing the same bug?
%it is possible but unlikely to reveal different ones, since it never re-order statement,
%never create new values}

Although the simplified test output by \SimpleTest still satisfies the
same predicate $\phi$ as the
original one, it is possible but \textit{unlikely} that the simplified
test exhibits different behavior than the un-simplified test, such as
revealing a different bug which
 happens to satisfy $\phi$. To avoid this, \SimpleTest relies on
programmers to provide a more specific $\phi$ which can adequately
capture the intended test behavior. How to avoid this issue
\textit{automatically} is
future work.

\SimpleTest uses a basic assumption that a shorter test that
reveals the same property is easier to understand by programmers.
We believe this assumption is intuitive and reasonable.
%in the context of the \SimpleTest algorithm.
\SimpleTest does not create new statements, re-order existing statements
or use new values in the simplified tests. All
input variables are reused from the original test code.  Thus,
the simplified test is unlikely to increase test code complexity.




There are several tradeoffs in the design of \SimpleTest. The algorithm  in Figure~\ref{fig:algorithm2}
chooses to reconstruct a simpler test by \textit{reusing} existing values, instead
of \textit{generating} new ones for replacement.
There are two primary reasons for this strategy. First,
\SimpleTest aims to simplify an existing test, thus it should
avoid changing the existing testing intentions. Generating new values
for replacement may still exhibit the same property, but
can substantially change the testing logic of the original test code. Second,
the search space of seeking a replacement candidate through generating new values
is technically infinite, while reusing values from the existing test has a much smaller
search space and is tractable in practice.
